package Chapter04;
// 將 StepIntoJava.java 內容替換為下列代碼即可運行
//======================================================================
//public class StepIntoJava {
//	public static void main(String[] args) {
//		Recursion app = new Recursion();
//		app.run();
//	}	
//}
//======================================================================

public class Recursion {

	int[] fibnums = new int[50];	// fibType2 用來記錄計算結果的表格
	int count1 = 0;	// 用來計算 fibType1 執行次數的 counter (計數器)
	int count2 = 0; // 用來計算 fibType2 執行次數的 counter (計數器)
	
	public void run() {
		// 階乘範例
		int x = 7;
		System.out.println("Type 1)"+x+"! = " + multiply1(x));
		System.out.println("Type 2)"+x+"! = " + multiply2(x));
		
		// 費布納西數列
		for (int i = 0; i < fibnums.length; i++) {
			fibnums[i] = -1;
		}
		x = 20;
		// 比較 fibType1, fibType2 兩種方式的方法呼叫次數
		System.out.printf("方法1: f(%d)=%d \t count=%d\n", x, fibType1(x), count1);
		System.out.printf("方法2: f(%d)=%d \t count=%d\n", x, fibType2(x), count2);
	}
	
	// Type1: 遞迴單純計算
	public int fibType1(int x) {
		count1 = count1 + 1;
		if (x == 1 || x == 2) {
			return 1;
		} else {
			return fibType1(x-1)+fibType1(x-2);
		}
	}
	
	// Type2: 遞迴利用表格
	public int fibType2(int x) {
		count2 = count2 + 1;
		if (fibnums[x] == -1) { // 如果不在表格裡面
			if (x == 1 || x == 2) {
		  		fibnums[x] = 1;
			} else {
				fibnums[x] = fibType2(x-1)+fibType2(x-2);
			}
		}
		return fibnums[x];
	}
	
	// 階乘計算：利用迴圈
	public int multiply1(int x) {
		int sum = 1;
		for (int i = x; i >= 1; i--) {
			sum = i * sum;
		}
		return sum;
	}
	
	// 階乘計算：利用遞迴
	public int multiply2(int x) {
		if (x == 1) {
			return 1;
		} else {
			System.out.println("in method: x ="+x);
			return x * multiply2(x-1);
		}
	}
}
